#include <iostream>

using namespace std;

// 二叉搜索树的实现
// 最重要的三种操作:查找、插入、删除

typedef struct TreeNode
{
    int value;
    struct TreeNode* lChild;
    struct TreeNode* rChild; 
}TreeNode;

class binarySearchTree
{
    public:
        binarySearchTree(int arr[],int arrLength);

        void inorderSearch(TreeNode* node);
        TreeNode* getRoot()
        {
            return this->root;
        };
        TreeNode* insertNode(TreeNode*,int);
        TreeNode* deleteNode(TreeNode*,int);
        TreeNode* getDeepNode(TreeNode*);

    private:
        int TreeLength;
        TreeNode* root;
        TreeNode* helpBuildTree(TreeNode* node,int value);
};

TreeNode* binarySearchTree::getDeepNode(TreeNode* n)
{
    TreeNode* reNode=n->rChild;
    while(reNode->lChild!=NULL)
    {
        reNode=reNode->lChild;
    }
    return reNode;
}

void binarySearchTree::inorderSearch(TreeNode* node)
{
    if(node->lChild!=NULL)
    {
        this->inorderSearch(node->lChild);
    }
    cout<<node->value<<' ';
    if(node->rChild!=NULL)
    {
        this->inorderSearch(node->rChild);
    }
}

TreeNode* binarySearchTree::helpBuildTree(TreeNode* node,int value)
{
    if(node==NULL)
    {
        node=new TreeNode;
        node->value=value;
        node->lChild=NULL;
        node->rChild=NULL;

    }
    else if(node->value<value)
    {
        node->rChild=this->helpBuildTree(node->rChild,value);
    }
    else
    {
        node->lChild=this->helpBuildTree(node->lChild,value);
    }
        return node;
}

binarySearchTree::binarySearchTree(int arr[],int arrLength)
{
    this->root=new TreeNode;
    this->root->value=arr[0];
    this->root->lChild=NULL;
    this->root->rChild=NULL;
    for(int i=1;i<arrLength;i++)
    {
        helpBuildTree(this->root,arr[i]);
    }
}

TreeNode* binarySearchTree::insertNode(TreeNode* node,int value)
{
    if(node==NULL)
    {
        node=new TreeNode;
        node->value=value;
        node->lChild=NULL;
        node->rChild=NULL;
    }
    else if(node->value<value)
    {
        node->rChild=insertNode(node->rChild,value);
    }
    else
    {
        node->lChild=insertNode(node->lChild,value);
    }
    return node;
}

TreeNode* binarySearchTree::deleteNode(TreeNode* node,int value)
{
    // 表示没有找到
    if(node==NULL)
    {
        return NULL;
    }
    if(node->value>value)
    {
        node->lChild=deleteNode(node->lChild,value);
    }
    else if(node->value<value)
    {
        node->rChild=deleteNode(node->rChild,value);
    }
    else
    {
        //如果是叶子结点
        if(node->lChild==NULL && node->rChild==NULL)
        {
            delete node;
            return NULL;
        }
        // 如果只有一个孩子结点
        if(node->rChild==NULL)
        {
            TreeNode* tempNode=node->lChild;
            delete node;
            return tempNode;
        }
        else if(node->lChild==NULL)
        {
            TreeNode* tempNode=node->rChild;
            delete node;
            return tempNode;
        }
        // 如果有两个结点
        else
        {
            TreeNode* tempNode=this->getDeepNode(node);
            node->value=tempNode->value;
            node->rChild=this->deleteNode(node->rChild,tempNode->value);
        }
    }
    return node;
}

int main()
{
    int arr[8]={90,12,14,1,4,46,32,6};
    binarySearchTree tree(arr,8);
    tree.inorderSearch(tree.getRoot());

    tree.insertNode(tree.getRoot(),50);
    tree.insertNode(tree.getRoot(),55);
    cout<<endl;
    tree.inorderSearch(tree.getRoot());

    tree.deleteNode(tree.getRoot(),50);
    tree.deleteNode(tree.getRoot(),55);
    cout<<endl;
    tree.inorderSearch(tree.getRoot());
    cout<<endl;
}